﻿#region LICENSE
/****************************************************************************
 *                                                                          *
 *  CoderBlu.Collections - Thread-safe Collections                          *
 *  Copyright (C) 2008 Rodger "Nullz" Aiken <nullz.void@gmail.com>          *
 *                                                                          *
 *  This library is free software; you can redistribute it and/or modify    *
 *  it under the terms of the GNU Library General Public License as         *
 *  published by the Free Software Foundation; either version 2 of the      *
 *  License, or (at your option) any later version.                         *
 *                                                                          *
 *  This library is distributed in the hope that it will be useful, but     *
 *  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANT     *
 *  ABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library        *
 *  General Public License for more details.                                *
 *                                                                          *
 *  You should have received a copy of the GNU Library General Public       *
 *  License along with this library; if not, write to the Free Foundation,  *
 *  Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA        *
 *                                                                          *
 ****************************************************************************/
#endregion

using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.Serialization;
using System.Security.Permissions;

namespace CoderBlu.Collections
{
	[Serializable]
	public class Deque : Deque<object>
	{
		public Deque ( )
			: base() {
		}
		public Deque ( int capacity )
			: base(capacity) {
		}
		public Deque ( IEnumerable collection )
			: base() {
			if ( collection == null )
				throw new ArgumentNullException("collection");

			foreach ( object item in collection )
				this.Push(item);
		}
		public Deque ( IEnumerable<object> collection )
			: base(collection) {
		}

		protected Deque ( SerializationInfo info, StreamingContext context )
			: base(info, context) {
		}
	}

	[Serializable]
	public class Deque<T> :
		SynchronizedCollection,
		ICollection,
		IEnumerable, IEnumerable<T>,
		ISerializable, IDeserializationCallback
	{
		private SerializationInfo _info;
		private T [ ] _items;
		private volatile int _head;
		private volatile int _size;

		public Deque ( )
			: this(0) {
		}
		public Deque ( int capacity ) {
			if ( capacity < 0 )
				throw new ArgumentOutOfRangeException("capacity");

			this._items = new T [ capacity ];
		}
		public Deque ( IEnumerable<T> collection )
			: this() {
			if ( collection == null )
				throw new ArgumentNullException("collection");

			foreach ( T item in collection )
				this.Push(item);
		}

		protected Deque ( SerializationInfo info, StreamingContext context ) {
			this._info = info;
		}

		public int Count {
			get { return this._size; }
		}

		public T First {
			get {
				if ( this._size < 1 )
					throw new InvalidOperationException();

				lock ( this._synclock )
					return this._items [ this._head ];
			}
		}

		public T Last {
			get {
				if ( this._size < 1 )
					throw new InvalidOperationException();

				lock ( this._synclock )
					return this._items [ this._head + ( this._size - 1 ) ];
			}
		}

		bool ICollection.IsSynchronized {
			get { return true; }
		}

		object ICollection.SyncRoot {
			get { return this; }
		}

		public void Clear ( ) {
			if ( this._size > 0 ) {
				lock ( this._synclock )
					Array.Clear(this._items, this._head, this._size);
			}
		}

		public bool Contains ( T item ) {
			if ( this._size > 0 ) {
				lock ( this._synclock )
					return ( Array.IndexOf<T>(this._items, item, this._head, this._size) >= 0 );
			}

			return false;
		}

		public void CopyTo ( T [ ] array ) {
			this.CopyTo(array, 0);
		}
		public void CopyTo ( T [ ] array, int arrayIndex ) {
			if ( array == null )
				throw new ArgumentNullException("array");

			if ( ( arrayIndex < 0 ) || ( arrayIndex >= array.Length ) )
				throw new ArgumentOutOfRangeException("arrayIndex");

			if ( this._size > 0 ) {
				lock ( this._synclock )
					Array.Copy(this._items, this._head, array, arrayIndex, Math.Min(( array.Length - arrayIndex ), this._size));
			}
		}

		public T Pop ( ) {
			if ( this._size < 1 )
				throw new InvalidOperationException();

			lock ( this._synclock ) {
				T item = this._items [ this._head + ( this._size - 1 ) ];
				this._items [ this._head + ( this._size - 1 ) ] = default(T);
				this._size--;
				return item;
			}
		}

		public void Push ( T item ) {
			lock ( this._synclock ) {
				if ( ( this._size + 1 ) > this._items.Length ) {
					if ( this._head > 0 ) {
						if ( this._size > 0 )
							Array.Copy(this._items, this._head, this._items, 0, this._size);
					} else {
						Array.Resize<T>(ref this._items, ( ( this._items.Length << 1 ) | 1 ));
					}
				}

				this._items [ this._head + this._size++ ] = item;
			}
		}

		public T Shift ( ) {
			if ( this._size < 1 )
				throw new InvalidOperationException();

			lock ( this._synclock ) {
				T item = this._items [ this._head ];
				this._items [ this._head ] = default(T);
				this._size--;

				if ( ++this._head >= this._items.Length )
					this._head = 0;

				return item;
			}
		}

		public void Unshift ( T item ) {
			lock ( this._synclock ) {
				if ( this._head > 0 ) {
					this._items [ --this._head ] = item;
				} else {
					if ( ( this._size + 1 ) > this._items.Length )
						Array.Resize<T>(ref this._items, ( ( this._items.Length << 1 ) | 1 ));

					if ( this._size > 0 )
						Array.Copy(this._items, 0, this._items, 1, this._size);

					this._items [ 0 ] = item;
				}

				this._size++;
			}
		}

		public IEnumerator<T> GetEnumerator ( ) {
			lock ( this._synclock ) {
				for ( int i = this._head ; i < this._size ; i++ )
					yield return this._items [ i ];
			}
		}

		[SecurityPermission(SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
		public virtual void GetObjectData ( SerializationInfo info, StreamingContext context ) {
			if ( info == null )
				throw new ArgumentNullException("info");

			lock ( this._synclock )
				info.AddValue("items", this.ToArray());
		}

		public virtual void OnDeserialization ( object sender ) {
			lock ( this._synclock ) {
				if ( this._info != null ) {
					T [ ] items = ( ( T [ ] ) this._info.GetValue("items", typeof(T [ ])) );
					this._items = new T [ ( ( items.Length << 1 ) | 1 ) ];
					this._head = 0;
					this._size = items.Length;

					Array.Copy(items, 0, this._items, 0, items.Length);

					this._info = null;
				}
			}
		}

		public T [ ] ToArray ( ) {
			lock ( this._synclock ) {
				T [ ] array = new T [ this._size ];

				this.CopyTo(array);
				return array;
			}
		}

		public void TrimExcess ( ) {
			lock ( this._synclock ) {
				this._items = this.ToArray();
				this._head = 0;
				this._size = this._items.Length;
			}
		}

		void ICollection.CopyTo ( Array array, int index ) {
			if ( array == null )
				throw new ArgumentNullException("array");

			if ( ( index < 0 ) || ( index >= array.Length ) )
				throw new ArgumentOutOfRangeException("index");

			if ( this._size > 0 ) {
				lock ( this._synclock )
					Array.ConstrainedCopy(this._items, this._head, array, index, Math.Min(( array.Length - index ), this._size));
			}
		}

		IEnumerator IEnumerable.GetEnumerator ( ) {
			return this.GetEnumerator();
		}
	}
}